Chmury [A]

Limit pamięci: 64 MB

Co za pech! Właśnie dzisiaj Profesor Bajtazar postanowił za pomocą specjalnego działka laserowego nawiązać pierwszy w historii ludzkości kontakt z kosmitami, lecz niestety niebo jest gęsto pokryte chmurami. Profesor nie wie jeszcze, w którym dokładnie miejscu najlepiej będzie postawić działko, nie jest on w stanie przewidzieć również, w którą stronę powieje wiatr. Bajtazar zastanawia się, ile maksymalnie przerw w transmisji komunikatów w kosmos mogą spowodować chmury (przy najbardziej pesymistycznej kombinacji ustawienia działka i kierunku wiatru).

Dla uproszczenia załóżmy, że chmury znajdujące się na bajtockim niebie mają kształt wielokątów prostych, zawierających brzeg oraz że żadne dwie różne chmury nie mają wspólnych punktów. Wiatr w Bajtocji, jak już zaczyna wiać, to wieje cały czas w tym samym kierunku i powoduje przemieszczanie się wszystkich chmur z tym samym wektorem prędkości. Działko Bajtazara można utożsamiać z jednym punktem; emituje ono promieniowanie laserowe nieprzerwanie pionowo do góry. Przerwa w transmisji następuje wtedy, kiedy promień lasera jest przysłonięty przez jakąś chmurę.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis ułożenia chmur na bajtockim niebie,
• wyznaczy maksymalną możliwą liczbę przerw w komunikacji z kosmitami, jakie mogą się przydarzyć Profesorowi Bajtazarowi,
• wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą dodatnią , oznaczającą liczbę chmur na bajtockim niebie. Kolejne wierszy zawiera opisy chmur, po jednym w wierszu. Każdy z nich składa się z liczby całkowitej (), oznaczającej liczbę boków wielokąta reprezentującego chmurę oraz z liczb całkowitych, pooddzielanych pojedynczymi odstępami i oznaczających współrzędne kartezjańskie wierzchołków wielokąta na niebie. Wszystkie współrzędne będą należeć do przedziału . Łączna liczba wierzchołków chmur będzie niewiększa niż .

Wyjście

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbą całkowitą, oznaczającą maksymalną możliwą liczbę przerw w kominikacji Bajtazara z kosmitami.

Przykład

Dla danych wejściowych:

2
5 1 1 5 1 5 4 3 2 1 4
3 2 4 3 5 4 4

poprawną odpowiedzią jest:

3

W przypadku umieszczenia lasera w punkcie i wiatru wiejącego w kierunku wektora nastąpiłyby 2 przerwy w transmisji. Maksymalna liczba przerw w transmisji (3) może się przydarzyć na przykład wtedy, gdy działko zostanie umieszczone w punkcie , a wiatr będzie wiał w kierunku wektora .

Autorzy zadania: Marcin Pilipczuk, Jakub Radoszewski, Piotr Stańczyk.